The present invention relates generally to computer security, and more specifically to generating an approximately uniform duty cycle in a random number generator.
Random number generator circuits are used in a variety of electronic applications. One important application for random number generators is in the field of computer security where message data is encrypted and decrypted. Cryptography involves the transformation of data into a coded message that is to be sent to and decoded only by the intended recipient. Most common cryptographic techniques use ciphers (or xe2x80x9ckeysxe2x80x9d) used by the sender to encode the message and by the receiver to decode the encoded message. Common cipher systems use either a single key, one to code and decode a message, or two keys, one to encode the message and the other to decode the message.
The keys used to encode and decode messages are basically binary data patterns against which a message is processed or filtered. Effective cipher systems require the use of keys that have a sufficiently high number of bits to make replication of a key nearly impossible. Furthermore, the data patterns comprising the keys must be sufficiently random so that their pattern or the patterns in the message encoded by the key cannot be predicted. Effective cryptographic systems thus require the use of high quality random number generators to ensure that the binary data within a message is transformed in a totally unpredictable manner. In general, any lack of randomness in an encryption scheme produces some degree of correlation between the coded and uncoded data. This correlation can then be used crack the code through techniques such as iterative trial and error predictions of possible output patterns based on a coded message.
A desirable feature of a binary random number generator is that it output one and zero bits in a purely random order. Thus, the value of the output bit at any given time should be totally unpredictable. It is desirable that the duty cycle of the output of the random number generator be approximately fifty percent over an infinite sample size, so that the chance of an output being a logic low (zero) is equal to the chance of the output being a logic high (one). It is also desirable for a random number generator to exhibit low correlation (e.g., approximately zero correlation) between any bit and any other bit, and a flat Fourier distribution among the output bits.
Present known random number generators, however, have a tendency to generate an uneven number of zeros or ones over a statistically significant sample size. A common reason for prior art random number generators to exhibit an unequal duty cycle is that the latches comprising the random number generator typically favor one of the two states if data is latched during a forbidden setup/hold time. A common present method of decreasing duty cycle variations in random number generators involves the use of a Linear Feedback Shift Register (LFSR) at the output stage of a random bit source.
FIG. 1 illustrates an example of a prior art random number generator that uses a Linear Feedback Shift Register 104 coupled to the output of a random bit source 102. LFSR 104 comprises a number of latches 105 and gates 106 through which the output bits from random bit source 102 are propagated. The states of the output bits are randomly inverted by gates 106, and the order of the bits is further mixed up through feed-back of the bits through latches 105.
In general, Linear Feedback Shift Registers, such as that illustrated in FIG. 1 possess certain disadvantages and do not fully correct non-level duty cycle characteristics exhibited by typical random bit sources. As illustrated by. LFSR 104, a typical LFSR itself comprises a number of latches and gates. These latches and gates will tend to exhibit the same propensity to latch a zero or one in certain circumstances, as the latches in the random bit source 102. Therefore, a typical LFSR does not itself produce a uniform duty cycle output of ones and zeros, and thus cannot entirely correct any duty cycle variations in a random bit source.
A further disadvantage of Linear Feedback Shift Registers is the requirement of a large number of latches and gates. For example, a 32-bit LFSR, such as shown in FIG. 1, requires 32 D-type latches, as well as a number of combinatorial gates. This adds significantly to the amount of silicon area required for a random number generator circuit that uses such an LFSR.
A method and apparatus is disclosed for producing a corrected bit stream from a random bit stream output by a random bit source. Sequential pairs of bits in the random bit stream are compared. If both bits in a pair of bits are identical, the output bits are discarded. If both bits in a pair of bits are different, one bit of the pair of bits is taken as the output bit.